import java.util.*;

/**
 * @author LKQ
 * @date 2022/4/10 9:57
 * @description 动态规划
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.minDistance("sea", "eat");
    }

    public int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        char[] w1 = word1.toCharArray(), w2 = word2.toCharArray();
        // dp[i][j] 代表 A[0..i]和 B[0..j]需要删除的长度使得两个字符串相同
        int[][] dp = new int[m + 1][n + 1];
        // 当 i = 0 || j = 0 时， 即其中一个字符串为空，那么需要全部删除 m + n
        for (int i = 0; i <= m; i++) {
            dp[i][0] = m + n;
        }
        for (int i = 0; i <= n; i++) {
            dp[0][i] = m + n;
        }
        for(int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (w1[i-1] == w2[j-1]) {
                    // 当 A[i-1] = B[j-1] 时，那么不需要减少这两个字母
                    dp[i][j] = dp[i-1][j-1] - 2;
                }else {
                    // 不同时，那么最少删除为，两者最小值
                    dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        return dp[m][n];
    }
}
